package cn.com.colasoft.dataStructure;

/**
 * 归并排序
 * 时间复杂度:O(logn)
 * 空间复杂度:O(n)
 *
 * @author lizhitao
 * @date 2018/5/13
 */
public class MergeSort {

    public void mergeSort(int[] array) {
        if (array == null || array.length == 0) {
            return ;
        }
        int left = 0;
        int right = array.length - 1;
        int[] helpArray = new int[array.length];
        mergeSort(array, helpArray, left, right);
    }

    private void mergeSort(int[] array, int[] helpArray, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(array, helpArray, left, mid);
        mergeSort(array, helpArray, mid + 1, right);
        merge(array, helpArray, left, mid, right);
    }

    void merge(int[] array, int[] helpArray, int left, int mid, int right) {

        // 将当前需要排序的元素复制到helpArray中.在helpArray中完成当前某一部分的元素排序
        for (int i = left; i <= right; i++) {
            helpArray[i] = array[i];
        }

        // 将当前需要比较的helpArray中的元素分为两截,进行一一对比排序
        int leftIdx = left;
        int rightIdx = mid + 1;
        while (leftIdx <= mid && rightIdx <= right) {

            if (helpArray[leftIdx] >= helpArray[rightIdx]) {
                array[left++] = helpArray[rightIdx++];
            } else {
                array[left++] = helpArray[leftIdx++];
            }
        }

        // 按照从小到大的顺序排序,需要保证左边部分所有元素了.因为我们是从array中copy过来的元素,array中当前操作的每一小区域的数据都是从小到大排列的
        // 那么后面部分必定是有序的大数值部分.只需要处理左边部分.记住:所有的操作都是针对原始array操作的!!
        // 例如 4 5 9 | 1 2 3 6
        while (leftIdx <= mid) {
            array[left++] = helpArray[leftIdx++];
       }

    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 1, 8, 9, 7, 7, 12, 4};
        new MergeSort().mergeSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }
}
